package BinaryTree.Medium;


import Structures.BinaryTree;
import Structures.TreeNode;
import com.sun.source.tree.Tree;

import java.util.Stack;

public class LC0236 {

    /*private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }*/

    /**
     * 简单解法，在DFS过程中记录路径，找到p或q后返回。分别以p或q为目标进行搜寻。最后检查两条路径。
     * 时间复杂度为N，但是存在重复操作；实际耗时12ms。
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stackP = new Stack<>(), stackQ = new Stack<>();
        stackP.add(root);
        stackQ.add(root);
        stackP = dfs(root, p, stackP); // 获取根到p和q的路径
        stackQ = dfs(root, q, stackQ);
        TreeNode lastCommonAncestor = root;
        for (int i = 1; i < Math.min(stackP.size(), stackQ.size()); i++) {
            if (stackP.get(i).val != stackQ.get(i).val) break;
            else lastCommonAncestor = stackP.get(i);
        }

        return lastCommonAncestor;
    }

    /**
     * 这种解法先找到根到p的路径，然后反向遍历路径，以路径上的每个结点为根，搜索子树中是否有q。
     * 这种解法不会产生冗余操作，时间复杂度为N；实际耗时10ms。
     */
    public TreeNode lowestCommonAncestorOptimized(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stackP = new Stack<>();
        stackP.add(root);
        stackP = dfs(root, p, stackP); // 获取根到p的路径

        // 如果路径中存在q，则直接返回q
        for (TreeNode node : stackP) {
            if (node.val == q.val) return q;
        }

        TreeNode lastPop = new TreeNode(Integer.MIN_VALUE);
        // 从栈的末尾开始，开始搜寻每个结点的子树，如果能找到q，则返回当前考虑的结点
        while (!stackP.isEmpty()) {
            TreeNode node = stackP.pop();
            if (node.val == root.val) return root;

            if (node.left != null && node.left != lastPop) {
                if (dfs(node.left, q, new Stack<>()) != null) return node;
            }
            if (node.right != null && node.right != lastPop) {
                if (dfs(node.right, q, new Stack<>()) != null) return node;
            }

            lastPop = node; // 返回路径的上一级
        }

        return root; // 为了通过编译，题目数据保证不会到达此位置
    }

    private Stack<TreeNode> dfs(TreeNode node, TreeNode target, Stack<TreeNode> path) {
        if (target.val == node.val) return path;

        if (node.left != null) {
            path.push(node.left);
            Stack<TreeNode> leftPath = dfs(node.left, target, path);
            if (leftPath != null) return path;
            else path.pop();
        }
        if (node.right != null) {
            path.push(node.right);
            Stack<TreeNode> rightPath = dfs(node.right, target, path);
            if (rightPath != null) return path;
            else path.pop();
        }

        return null;
    }

    /**
     * \@Krahets的解法。这种解法需要分四种情况考虑DFS的返回值；但是是目前看到效率最高的解法。
     */
    public TreeNode lowestCommonAncestorOptimized2(TreeNode root, TreeNode p, TreeNode q) {
        return dfs(root, p, q);
    }

    /**
     * 深度优先搜索的返回值是p或q本身，或p和q的最深公共先祖；返回null表示子树中不存在p或q
     */
    private TreeNode dfs(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null) return null;
        if (node.val == p.val || node.val == q.val) return node;

        TreeNode left = dfs(node.left, p, q), right = dfs(node.right, p, q);
        if (left != null && right != null) return node; // p，q分别位于左右子树中，那么node就是要求的结点
        if (left == null && right == null) return null; // 该子树中不存在p或q

        // 如果p和q有一个在左子树中，那么left就是p或q本身；如果p和q均在左子树中，那么left是p和q的最深公共先祖
        // 可以模拟一下两种情况，验证其正确性
        if (left != null) return left;
        else return right; // left和right必有一个不为空
    }

    public static void main(String[] args) {
        Integer[] elements = new Integer[]{3, 5, 1, 6, 2, 0, 8, null, null, 7, 4};
        TreeNode root = BinaryTree.constructBinaryTree(elements);
        LC0236 solution = new LC0236();
        System.out.println(solution.lowestCommonAncestor(root, new TreeNode(5), new TreeNode(1)));
    }
}
